#include <stdio.h>
#include <stdlib.h>
/*
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

数据范围：链表长度 0 \le n \le 200000≤n≤20000 ，链表中每个节点的值满足 0 \le val \le 10000≤val≤1000

要求：空间复杂度 O(n)O(n) 并在链表上进行操作而不新建链表，时间复杂度 O(n)O(n)
进阶：空间复杂度 O(1)O(1) ， 时间复杂度 O(n)O(n)

输入：
{1,2,3,4}
复制
返回值：
{1,4,2,3}
复制
说明：
给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出
*/
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
LinkList ListInit(){
	LNode *head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL;
	return head;
}
LinkList ListCreate(LNode* head){ //采用头插法插入数据
	//头插法建立链表
	int data;
	printf("请输入链表数据,-1结束输入:\n");
	while(scanf("%d",&data) != EOF && data != -1){
		LNode *newNode = (LNode*)malloc(sizeof(LNode));
		newNode->data = data;
		newNode->next = head->next;
		head->next = newNode;
	}
	return head;
}
void ReorderList(LinkList head){ //重排链表
	LinkList p = head->next;
	int listLength = 0;
	while (p) { //先求出这个链表的长度。
		listLength++;         
		p = p->next;
	}
	int mid = listLength / 2;//指针二的起点次序
	LinkList start1 = NULL,start2 = NULL;
	p = head->next;
	int i = 0;
	while(p){ //找到中间节点
		if(i++ == mid){ 
			break;
		}
		p = p->next;
	}
	
}
void PrintList(LinkList head){
	LNode *p = head->next;
	while(p){
		printf("%d ",p->data);
		p = p->next;
	}
}
int main(int argc, char *argv[]) {
	LinkList list = ListInit();
	ListCreate(list);
	PrintList(list);
	ReorderList(list);
}